/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 八皇后问题;

/**
 * @Description 八皇后问题
 * 一个古老而著名的问题，是回溯算法的典型案例。
 * 该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：
 * 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，
 * 即：任意两个皇后都不能处于 同一行 、同一列 或 同一斜 线上，
 * 问有多少种摆法。
 * <p>
 * 八皇后问题算法思路分析
 * <p>
 * 1、第一个皇后先放第一行第一列
 * 2、第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
 * 3、继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
 * 4、当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
 * 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤
 * @Author 俊昭
 * @Date 2022/4/29
 */
public class EightQueens {
    private int[] board = new int[8];
    private int temp = 0;
    public void setQueen(int n) {
        if (n == 8) {
            for (int i : board) {
                System.out.print(i);
            }
            System.out.print("\t");
            temp++;
            return;
        }
        //
        for (int a = 0; a < 8; a++) {
            board[n] = a;
            if (isConflict(n)) {// 不冲突
                setQueen(n + 1);
            }
        }
    }

    public void show() {
        System.out.println(temp + "种解法");
    }

    /**
     * @param n 放入的 第n+1 个皇后(也就是皇后的索引为n)
     * @description 是否冲突
     * @date 2022/4/29
     */
    private boolean isConflict(int n) {
        for (int i = 0; i < n; i++) {
            // 同一列
            if (board[i] == board[n]) {
                return false;
            } else if (Math.abs(n - i) == Math.abs(board[n] - board[i])) {
                // 行差与列差相等即在一条斜线上
                return false;
            }
        }
        return true;
    }


}
